package stack_queue;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 225. 用队列实现栈
 * 使用一个队列实现栈
 * 使用两个队列实现栈
 *
 * @author Api
 * @date 2023/10/15 16:18
 */
public class Code225_ImplementingStackWithQueues {
    //==================================================================================================================
    // 使用两个 Queue 实现方法1
    static class MyStack1 {
        Queue<Integer> queue1; // 和栈中保持一样元素的队列
        Queue<Integer> queue2; // 辅助队列

        public MyStack1() {
            queue1 = new LinkedList<>();
            queue2 = new LinkedList<>();
        }

        public void push(int x) {
            queue2.offer(x); // 先放在辅助队列中
            while (!queue1.isEmpty()) {
                queue2.offer(queue1.poll());
            }
            Queue<Integer> queueTemp;
            queueTemp = queue1;
            queue1 = queue2;
            queue2 = queueTemp; // 最后交换queue1和queue2，将元素都放到queue1中
        }

        public int pop() {
            return queue1.poll(); // 因为queue1中的元素和栈中的保持一致，所以这个和下面两个的操作只看queue1即可
        }

        public int top() {
            return queue1.peek();
        }

        public boolean empty() {
            return queue1.isEmpty();
        }
    }

    //==================================================================================================================
    //使用两个 Queue 实现方法2
    static class MyStack2 {
        // q1作为主要的队列，其元素排列顺序和出栈顺序相同
        Queue<Integer> q1 = new ArrayDeque<>();
        // q2仅作为临时放置
        Queue<Integer> q2 = new ArrayDeque<>();

        public MyStack2() {

        }

        // 在加入元素时先将q1中的元素依次出栈压入q2，然后将新加入的元素压入q1，再将q2中的元素依次出栈压入q1
        public void push(int x) {
            while (q1.size() > 0) {
                q2.add(q1.poll());
            }
            q1.add(x);
            while (q2.size() > 0) {
                q1.add(q2.poll());
            }
        }

        public int pop() {
            return q1.poll();
        }

        public int top() {
            return q1.peek();
        }

        public boolean empty() {
            return q1.isEmpty();
        }
    }

    //==================================================================================================================
    // 使用两个Deque实现
    static class MyStack3 {
        // Deque接口继承了Queue接口
        // 所以Queue中的add、poll、peek等效于Deque中的addLast、pollFirst、peekFirst
        Deque<Integer> que1;
        Deque<Integer> que2;

        public MyStack3() {
            que1 = new ArrayDeque<>();
            que2 = new ArrayDeque<>();
        }

        public void push(int x) {
            que1.addLast(x);
        }

        public int pop() {
            int size = que1.size();
            size--;
            // 将que1导入que2，但留下最后一个值
            while (size-- > 0) {
                que2.addLast(que1.peekFirst());
                que1.pollFirst();
            }
            int res = que1.pollFirst();
            // 将que2对象的引用赋值给了que1，此时que1，que2指向同一个队列
            que1 = que2;
            // 如果直接操作que2，que1也会受到影响，所以为que2分配到一个新的空间
            que2 = new ArrayDeque<>();
            return res;
        }

        public int top() {
            return que1.peekLast();
        }

        public boolean empty() {
            return que1.isEmpty();
        }
    }

    //==================================================================================================================
    // 使用一个Deque实现
    static class MyStack4 {
        // Deque 接口继承了 Queue 接口
        // 所以 Queue 中的 add、poll、peek等效于 Deque 中的 addLast、pollFirst、peekFirst
        Deque<Integer> que1;

        public MyStack4() {
            que1 = new ArrayDeque<>();
        }

        public void push(int x) {
            que1.addLast(x);
        }

        public int pop() {
            int size = que1.size();
            size--;
            // 将que1导入que2，但留下最后一个值
            while (size-- > 0) {
                que1.addLast(que1.peekFirst());
                que1.pollFirst();
            }
            int res = que1.pollFirst();
            return res;
        }

        public int top() {
            return que1.peekLast();
        }

        public boolean empty() {
            return que1.isEmpty();
        }
    }

    //==================================================================================================================
    // 使用一个Queue实现
    static class MyStack5 {
        Queue<Integer> queue;

        public MyStack5() {
            queue = new LinkedList<>();
        }

        //每 offer 一个数（A）进来，都重新排列，把这个数（A）放到队列的队首
        public void push(int x) {
            queue.offer(x);
            int size = queue.size();
            //移动除了 A 的其它数
            while (size-- > 1) {
                queue.offer(queue.poll());
            }
        }

        public int pop() {
            return queue.poll();
        }

        public int top() {
            return queue.peek();
        }

        public boolean empty() {
            return queue.isEmpty();
        }
    }
    //==================================================================================================================
    // 使用一个Queue实现
    // 效率高和内存占用低
    static class MyStack {
        private final Queue<Integer> queue;

        public MyStack() {
            queue = new LinkedList<>();
        }

        public void push(int x) {
            queue.add(x);
            for (int i = 1; i < queue.size(); i++) {
                queue.add(queue.remove());
            }
        }

        public int pop() {
            return queue.remove();
        }

        public int top() {
            return queue.peek();
        }

        public boolean empty() {
            return queue.isEmpty();
        }
    }

    public static void main(String[] args) {
        MyStack myStack = new MyStack();
        myStack.push(1);
        myStack.push(2);
        myStack.pop();
        myStack.pop();
    }
}
